// 定义链表节点类
export class LinkedListNode<T> {
    key?: number;
    value: T;
    prev: LinkedListNode<T> | null = null;
    next: LinkedListNode<T> | null = null;

    constructor(value: T, key: number = 0) { // 默认值为0，保证总是有值
        this.value = value;
        this.key = key;
    }
}

/**
 * 可变链表数据结构，支持双向链表操作和键值映射
 */
export class LinkedList<T> {
    private map: Map<number, LinkedListNode<T>>  = new Map<number, LinkedListNode<T>>();
    private head: LinkedListNode<T> | null = null;
    private tail: LinkedListNode<T> | null = null;
    private id: number = 0;
    private length: number = 0;

    /**
     * 获取并自增内部ID计数器
     * @returns 当前ID值
     */
    public getNextId(): number {
        return ++this.id;
    }

    /**
     * 获取链表的当前长度
     * @returns 链表中的节点数量
     */
    public getLength(): number {
        return this.length;
    }

    /**
     * 将新节点插入到指定节点之后的内部方法
     * @param newNode 要插入的新节点
     * @param prevNode 前一个节点(可选)，不提供则添加到链表尾部
     * @returns 插入的新节点
     */
    public insertNodeAfter(newNode: LinkedListNode<T>, prevNode?: LinkedListNode<T>): LinkedListNode<T> {
        if (prevNode) {
            // 在指定节点后插入
            newNode.prev = prevNode;
            newNode.next = prevNode.next;
            prevNode.next = newNode;
            
            if (newNode.next) {
                newNode.next.prev = newNode;
            } else {
                // 如果是在尾节点后插入，更新尾节点
                this.tail = newNode;
            }
        } else {
            // 添加到链表尾部
            if (this.tail) {
                // 非空链表，添加到尾部
                newNode.prev = this.tail;
                this.tail.next = newNode;
                this.tail = newNode;
            } else {
                // 空链表
                this.head = newNode;
                this.tail = newNode;
            }
        }
        
        this.length++;
        return newNode;
    }

    /**
     * 将新节点插入到指定节点之前的内部方法
     * @param newNode 要插入的新节点
     * @param nextNode 后一个节点(可选)，不提供则添加到链表头部
     * @returns 插入的新节点
     */
    private insertNodeBefore(newNode: LinkedListNode<T>, nextNode?: LinkedListNode<T>): LinkedListNode<T> {
        if (nextNode) {
            // 在指定节点前插入
            newNode.next = nextNode;
            newNode.prev = nextNode.prev;
            
            if (newNode.prev) {
                newNode.prev.next = newNode;
            } else {
                // 如果是在头节点前插入，更新头节点
                this.head = newNode;
            }
            
            nextNode.prev = newNode;
        } else {
            // 添加到链表头部
            if (this.head) {
                // 非空链表，添加到头部
                newNode.next = this.head;
                this.head.prev = newNode;
                this.head = newNode;
            } else {
                // 空链表
                this.head = newNode;
                this.tail = newNode;
            }
        }
        
        this.length++;
        return newNode;
    }

    /**
     * 使用指定键将值添加到链表中指定节点之后，并添加到映射中
     * @param key 用于在map中标识节点的唯一键
     * @param value 要存储的值
     * @param prevNode 指定在哪个节点之后插入，不提供则添加到链表尾部
     */
    setAfter(key: number, value: T, prevNode?: LinkedListNode<T>) {
        const newNode = new LinkedListNode(value, key);
        
        // 添加到链表
        this.insertNodeAfter(newNode, prevNode);

        // 添加到map
        this.map.set(key, newNode);
        return newNode;
    }

    /**
     * 直接设置node
     * @param key key
     * @param node 节点
     */
    set(key: number, node: LinkedListNode<T>) {
        this.map.set(key, node);
    }

    /**
     * 向链表尾部添加一个值，自动生成键
     * @param value 要添加的值
     * @returns 为新节点生成的唯一键
     */
    append(value: T): number {
        const index = this.getNextId();
        this.setAfter(index, value);
        return index;
    }
    
    /**
     * 使用指定键将值添加到链表中指定节点之前，并添加到映射中
     * @param key 用于在map中标识节点的唯一键
     * @param value 要存储的值
     * @param nextNode 指定在哪个节点之前插入，不提供则添加到链表头部
     */
    setBefore(key: number, value: T, nextNode?: LinkedListNode<T>) {
        const newNode = new LinkedListNode(value, key);
        // 添加到链表
        this.insertNodeBefore(newNode, nextNode);
        // 添加到map
        this.map.set(key, newNode);
    }

    /**
     * 在链表中指定节点后插入新值（不会加入到映射中）
     * @param value 要插入的值
     * @param prev 指定在哪个节点之后插入，不提供则添加到链表尾部
     * @returns 新创建的节点
     */
    insertAfter(value: T, prev?: LinkedListNode<T>): LinkedListNode<T> {
        // insertAfter 创建的节点不会被加入到map中，所以不需要分配key
        const newNode = new LinkedListNode(value);
        return this.insertNodeAfter(newNode, prev);
    }

    /**
     * 在链表中指定节点前插入新值（不会加入到映射中）
     * @param value 要插入的值
     * @param node 指定在哪个节点之前插入，不提供则添加到链表头部
     * @returns 新创建的节点
     */
    insertBefore(value: T, node?: LinkedListNode<T>): LinkedListNode<T> {
        // insertBefore 创建的节点不会被加入到map中，所以不需要分配key
        const newNode = new LinkedListNode(value);
        return this.insertNodeBefore(newNode, node);
    }
    
    /**
     * 从链表中删除指定节点，并更新链表结构
     * @param node 要删除的节点
     * @returns 是否成功删除
     */
    removeNode(node: LinkedListNode<T>): boolean {
        // 更新链表连接
        if (node.prev) {
            node.prev.next = node.next;
        } else {
            // 如果是头节点
            this.head = node.next;
        }
        
        if (node.next) {
            node.next.prev = node.prev;
        } else {
            // 如果是尾节点
            this.tail = node.prev;
        }
        if (node.key) {
            this.map.delete(node.key);
        }
        
        this.length--;
        return true;
    }
    
    /**
     * 删除指定节点及其前后指定数量的节点
     * @param targetNode 目标节点（中心点）
     * @param beforeCount 目标节点之前要删除的节点数量
     * @param afterCount 目标节点之后要删除的节点数量
     * @returns 所有被删除节点的值组成的数组
     */
    removeNodeAround(targetNode: LinkedListNode<T>, beforeCount: number = 0, afterCount: number = 0): T[] {
        const deletedValues: T[] = [];
        
        // 删除目标节点之前的节点
        let currentNode = targetNode.prev;
        let countBefore = 0;
        
        while (currentNode && countBefore < beforeCount) {
            const nodeToRemove = currentNode;
            currentNode = currentNode.prev;
            
            // 保存要删除的节点值
            deletedValues.push(nodeToRemove.value);
            
            this.removeNode(nodeToRemove);
            
            countBefore++;
        }
        
        // 删除目标节点之后的节点
        currentNode = targetNode.next;
        let countAfter = 0;

        // 删除目标节点本身
        deletedValues.push(targetNode.value);
        this.removeNode(targetNode);
        
        while (currentNode && countAfter < afterCount) {
            const nodeToRemove = currentNode;
            currentNode = currentNode.next;
            
            // 保存要删除的节点值
            deletedValues.push(nodeToRemove.value);
            this.removeNode(nodeToRemove);
            countAfter++;
        }
        return deletedValues;
    }
    
    /**
     * 根据键从映射中获取对应节点
     * @param key 要查找的键
     * @returns 对应的链表节点，如果不存在则返回undefined
     */
    getNode(key: number): LinkedListNode<T> | undefined {
        return this.map.get(key);
    }
    
    /**
     * 获取链表的头节点
     * @returns 头节点，如果链表为空则返回null
     */
    getHead(): LinkedListNode<T> | null {
        return this.head;
    }
    
    /**
     * 获取链表的尾节点
     * @returns 尾节点，如果链表为空则返回null
     */
    getTail(): LinkedListNode<T> | null {
        return this.tail;
    }

    /**
     * 根据键删除对应节点及其前后指定数量的节点
     * @param key 要删除的目标节点的键
     * @param beforeCount 目标节点之前要删除的节点数量
     * @param afterCount 目标节点之后要删除的节点数量
     * @returns 所有被删除节点的值组成的数组，如果未找到目标节点则返回空数组
     */
    removeNodeAroundByKey(key: number, beforeCount: number = 0, afterCount: number = 0): T[] {
        const node = this.getNode(key);
        if (!node) {
            return [];
        }
        return this.removeNodeAround(node, beforeCount, afterCount);
    }

    /**
     * 检查链表是否为空
     * @returns 如果链表中没有节点则返回true，否则返回false
     */
    isEmpty(): boolean {
        return this.length === 0;
    }
    
    /**
     * 清空链表和映射的所有数据
     */
    clear(): void {
        this.head = null;
        this.tail = null;
        this.map.clear();
        this.length = 0;
    }

    /**
     * 从head开始遍历链表中的所有节点，对每个节点执行回调函数
     * @param callback 对每个节点执行的回调函数
     */
    forEach(callback: (node: LinkedListNode<T>) => boolean | void): void {
        let currentNode = this.head;
        while (currentNode) {
            if (callback(currentNode) === false) {
                break;
            }
            currentNode = currentNode.next;
        }
    }
}

export class NodeCursor<T> {
  private currentNode: LinkedListNode<T>;
  private offset: number = 0;

  constructor(currentNode: LinkedListNode<T>) {
    this.currentNode = currentNode;
  }

  public getCurrentNode(): LinkedListNode<T> {
    return this.currentNode;
  }

  /**
   * 获取开始位置和结束位置之间的节点列表，前闭后开，start和end相等时返回空
   * @param start 开始位置
   * @param end 结束位置
   * @returns 节点列表
   */
  public getNodeList(start: number, end: number): LinkedListNode<T>[] {
    this.go(start);
    return this.moveToNext(end);
  }

  /**
   * 获取移动路径上的所有节点
   * @param offset 目标位置，不包含目标位置
   * @returns 包含当前节点和移动路径上所有节点的数组
   */
  public moveToNext(offset: number): LinkedListNode<T>[] {
    const diff = offset - this.offset;
    if (diff === 0) {
      return []; // 不需要移动
    }

    if (diff < 0) {
        throw new Error("offset must be greater than current offset");
    }

    const nodes: LinkedListNode<T>[] = []; // 包含起始节点
    let node = this.currentNode;
    for (let i = 0; i < diff; i++) {
        nodes.push(node);
        const next = node.next;
        if (next) {
            node = next;
        } else {
            break; // 无法继续移动，跳出循环
        }
    }
    return nodes;
  }

  public go(offset: number) {
    const diff = offset - this.offset;  // 修正计算方向：目标位置减当前位置
    if (diff === 0) {
        return;
    }

    let actualMovedSteps = 0;  // 实际移动的步数
    if (diff > 0) {  // 向后移动（next方向）
        for (let i = 0; i < diff; i++) {
            const next = this.currentNode.next;
            if (next) {
                this.currentNode = next;
                actualMovedSteps++;
            } else {
                break;  // 无法继续移动，跳出循环
            }
        }
    } else {  // 向前移动（prev方向）
        for (let i = 0; i < -diff; i++) {  // diff为负数，取绝对值
            const prev = this.currentNode.prev;
            if (prev) {
                this.currentNode = prev;
                actualMovedSteps--;  // 向前移动，步数为负
            } else {
                break;  // 无法继续移动，跳出循环
            }
        }
    }

    // 根据实际移动的步数更新offset
    this.offset += actualMovedSteps;
  }

}